package leetcode.code1829;

import leetcode.helper.MaxDebug;

public class Solution extends Solution1829 {

	@Override
	public int[] getMaximumXor(int[] nums, int maximumBit) {
		// maximumBit使得尾部能达到的最大值。如maximumBit==2 max==11
		int max = (1 << maximumBit) - 1;
		int xor = 0; // 所有数的异或和
		for (int num : nums) {
			xor ^= num;
		}
		xor &= max;// 结果是max所有位上的数字，与xor中超过max位的数字无关
		// 比如xor是11000，max是11，结果就是00上能达到最大，与前缀110无关，所以xor&max去掉xor无用的部分
		int LEN = nums.length;
		int ans[] = new int[LEN];
		for (int i = 0; i < LEN; i++) {
			ans[i] = xor ^ max;// xor ^ ans[i] = max -> xor ^ xor ^ ans[i] = xor ^ max
			xor ^= nums[LEN - 1 - i];// 从异或和中去掉最后一个数字
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		MaxDebug.debug14(so);

	}

}
